package Task43;

import javax.security.auth.callback.CallbackHandler;
import java.util.*;

/**
 *  输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
 * 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
 * ABC BAC CAB ACB CBA
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String string = "ABC";
        ArrayList<String> arrayList = Permutation(string);
        for(String str: arrayList) {
            System.out.print(str+" ");
        }
    }
    public static ArrayList<String> Permutation(String str){
        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            Collections.sort(list);
        }
        return list;
    }
    private static void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            for(int j=i;j<chars.length;++j){
                if(j==i || !charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }
    public static void swap(char[] chars,int start, int end){
        char ch = chars[start];
        chars[start] = chars[end];
        chars[end] = ch;
    }
}
